# Link: https://leetcode.com/problems/di-string-match/submissions/ 942. 增减字符串匹配
class Solution:
    def diStringMatch(self, S):
        """
        :type S: str
        :rtype: List[int]
        """
        begin, end = 0, len(S)
        result = []
        for i in S:
            if i == 'I':
                result.append(begin)
                begin += 1
            else:
                result.append(end)
                end -= 1
        return result + [begin]